package 力扣_二分查找.旋转数组系列.特例;

/**
 * @author zx
 * @create 2022-10-12 20:04
 */
public class 寻找旋转排序数组中的最小值_153 {
    /**
     * 三道题属于两种题,但是代码都是官方代码，答案一样，背就行
     */
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            // 说明 [mid, right] 是递增区间(因为旋转数组的局部有序性)
            // 最小值一定在 [left, mid] 范围内(包括mid本身), 因此缩小右边界：right = mid
            if(nums[mid] < nums[right]) {
                right = mid;
            // 说明[left, mid]是递增区间,而最小值一定在 [mid+1...right] 范围内(因为mid不可能是最小值)
            // 因此缩小左边界：left = mid + 1
            }else if(nums[mid] > nums[right]){
                left = mid + 1;
            // 处理重复元素的关键逻辑：当中间值与右边界值相等时, 无法判断最小值在哪一侧(right--)
            // 因为即使 nums[right] 是最小值, nums[mid] 也是相同的值, 不会丢失最小值
            }else if(nums[mid] == nums[right]){
                right--;
            }
        }
        return nums[left];
    }
}
